package com.xuyuan.arithmetic.datastructure.quest;

import org.junit.jupiter.api.Test;

import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.Stream;

/**
 * 滑动窗口算法
 *
 * @author xuyuan
 * <p>
 * 最值问题、固定长度的子数组问题‌、‌字符串模式匹配‌、累积和或乘积。
 * <p>
 * 解题步骤：‌定义窗口控制变量、进窗口操作‌、出窗口操作、‌更新结果(画图)
 */
public class SlidingWindowSolution {
    /**
     * 最长无重复字串
     */
    int longestSubstring(String str) {
        int[] count = new int[256];
        int max = 0, left = 0;
        for (int i = 0; i < str.length(); i++) {
            count[str.charAt(i)]++;
            while (count[str.charAt(i)] > 1) {
                count[str.charAt(left)]--;
                left++;
            }
            max = Math.max(max, i - left + 1);
        }
        return max;
    }

    /**
     * @desc 找出所有的字母异位词
     * 给定两个字符串 s 和 p，找到 s 中所有 p 的异位词的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
     * 字母异位词是通过重新排列不同单词或短语的字母而形成的单词或短语，并使用所有原字母一次。
     * <p>
     * 示例 1:
     * 输入: s = "cbaebabacd", p = "abc"
     * 输出: [0,6]
     * 解释:
     * 起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
     * 起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。
     * <p>
     * 示例 2:
     * 输入: s = "abab", p = "ab"
     * 输出: [0,1,2]
     * 解释:
     * 起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
     * 起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
     * 起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。
     * <p>
     */
    List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new ArrayList<>();
        int sLen = s.length(), pLen = p.length();
        if (sLen < pLen) return res;
        int[] pCnt = new int[26], sCnt = new int[26];
        for (int i = 0; i < pLen; i++) {
            sCnt[s.charAt(i) - 'a']++;
            pCnt[p.charAt(i) - 'a']++;
        }
        if (Arrays.equals(sCnt, pCnt)) {
            res.add(0);
        }
        for (int i = pLen; i < sLen; i++) {
            sCnt[s.charAt(i - pLen) - 'a']--;
            sCnt[s.charAt(i) - 'a']++;
            if (Arrays.equals(sCnt, pCnt)) {
                res.add(i - pLen + 1);
            }
        }
        return res;
    }

    List<Integer> findAnagrams1(String s, String p) {
        int[] count = new int[256];
        List<Integer> result = new ArrayList<>();
        for (char c : p.toCharArray()) {
            count[c]++;
        }
        for (int i = 0; i < s.length(); i++) {
            int[] temp = Arrays.copyOf(count, 256);
            if (i + p.length() > s.length()) break;
            for (int j = i; j < i + p.length(); j++) {
                if (temp[s.charAt(j)] > 0) {
                    temp[s.charAt(j)]--;
                } else {
                    break;
                }
                if (j == i + p.length() - 1) result.add(i);
            }
        }
        return result;
    }

    /**
     * @desc 重复的DNA序列
     * <p>
     * 给定一个表示 DNA序列 的字符串 s ，返回所有在 DNA 分子中出现不止一次的 长度为 10 的序列(子字符串)。你可以按 任意顺序 返回答案。
     * <p>
     * 示例 1：
     * 输入：s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
     * 输出：["AAAAACCCCC","CCCCCAAAAA"]
     * <p>
     * 示例 2：
     * 输入：s = "AAAAAAAAAAAAA"
     * 输出：["AAAAAAAAAA"]
     */
    List<String> findRepeatedDnaSequences(String s) {
        int n = s.length();
        if (n <= 10) {
            return new ArrayList<>();
        }

        Set<String> seen = new HashSet<>();
        Set<String> res = new HashSet<>();

        for (int i = 0; i < n - 9; i++) {
            String cur = s.substring(i, i + 10);
            if (seen.contains(cur)) {
                res.add(cur);
            }
            seen.add(cur);
        }

        return new ArrayList<>(res);
    }

    /**
     * map
     */
    List<String> findRepeatedDnaSequences1(String s) {
        List<String> res = new ArrayList<>();
        if (s.length() <= 10) return res;
        Map<String, Integer> map = new HashMap<>();
        for (int i = 0; i + 10 <= s.length(); i++) {
            String substring = s.substring(i, i + 10);
            if (map.containsKey(substring)) {
                map.put(substring, map.get(substring) + 1);
            } else {
                map.put(substring, 1);
            }
        }
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            if (entry.getValue() > 1) {
                res.add(entry.getKey());
            }
        }
        return res;
    }

    /**
     * @desc 存在重复元素 II
     * 给你一个整数数组 nums 和一个整数 k ，判断数组中是否存在两个 不同的索引 i 和 j ，满足 nums[i] == nums[j] 且 abs(i - j) <= k 。
     * 如果存在，返回 true ；否则，返回 false 。
     * <p>
     * 示例 1：
     * 输入：nums = [1,2,3,1], k = 3
     * 输出：true
     * <p>
     * 示例 2：
     * 输入：nums = [1,0,1,1], k = 1
     * 输出：true
     * <p>
     * 示例 3：
     * 输入：nums = [1,2,3,1,2,3], k = 2
     * 输出：false
     * <p>
     * [1,2,2,3] 3
     */
    boolean containsNearbyDuplicate(int[] nums, int k) {
        Set<Integer> set = new HashSet<>();
        int length = nums.length;
        for (int i = 0; i < length; i++) {
            if (i > k) {
                set.remove(nums[i - k - 1]);
            }
            if (!set.add(nums[i])) {
                return true;
            }
        }
        return false;
    }

    boolean containsNearbyDuplicate1(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        int length = nums.length;
        for (int i = 0; i < length; i++) {
            int num = nums[i];
            if (map.containsKey(num) && i - map.get(num) <= k) {
                return true;
            }
            map.put(num, i);
        }
        return false;
    }

    /**
     * @desc 至少有 K 个重复字符的最长子串
     * 给你一个字符串 s 和一个整数 k ，请你找出 s 中的最长子串， 要求该子串中的每一字符出现次数都不少于 k 。返回这一子串的长度。
     * 如果不存在这样的子字符串，则返回 0。
     * <p>
     * 示例 1：
     * 输入：s = "aaabb", k = 3
     * 输出：3
     * 解释：最长子串为 "aaa" ，其中 'a' 重复了 3 次。
     * <p>
     * 示例 2：
     * 输入：s = "ababbc", k = 2
     * 输出：5
     * 解释：最长子串为 "ababb" ，其中 'a' 重复了 2 次， 'b' 重复了 3 次。
     */
    int longestSubstring(String s, int k) {
        int n = s.length();
        if (n < k) {
            return 0;
        }
        char[] cs = s.toCharArray();
        int[] cnt = new int[26];
        for (char c : cs) {
            cnt[c - 'a']++;
        }
        int l = 0;
        int res = 0;
        for (int r = 0; r < n; r++) {
            if (cnt[cs[r] - 'a'] < k) {
                res = Math.max(res, longestSubstring(s.substring(l, r), k));
                l = r + 1;
            }
        }
        // 注意到左边界l == 0时， s中所有字符均满足条件；否则补上最后一段子串
        return l == 0 ? n : Math.max(res, longestSubstring(s.substring(l, n), k));
    }

    /**
     * @desc 串联所有单词的子串
     * 给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串 长度相同。
     * s 中的 串联子串 是指一个包含  words 中所有字符串以任意顺序排列连接起来的子串。
     * <p>
     * 输入：s = "barfoothefoobarman", words = ["foo","bar"]
     * 输出：[0,9]
     * 解释：因为 words.length == 2 同时 words[i].length == 3，连接的子字符串的长度必须为 6。
     * 子串 "barfoo" 开始位置是 0。它是 words 中以 ["bar","foo"] 顺序排列的连接。
     * 子串 "foobar" 开始位置是 9。它是 words 中以 ["foo","bar"] 顺序排列的连接。
     * 输出顺序无关紧要。返回 [9,0] 也是可以的。
     */
    List<Integer> findSubstring(String s, String[] words) {
        List<Integer> res = new ArrayList<>();
        int count = words.length, len = words[0].length();
        int border = count * len, index;
        for (int i = 0; i < s.length() - border + 1; i++) {
            List<String> temp = Stream.of(words).collect(Collectors.toList());
            for (int j = 0; j < count; j++) {
                index = i + j * len;
                String sub = s.substring(index, index + len);
                if (temp.contains(sub)) {
                    temp.remove(sub);
                } else {
                    break;
                }
                if (temp.size() == 0) res.add(i);
            }
        }
        return res;
    }

    List<Integer> findSubstring1(String s, String[] words) {
        List<Integer> res = new ArrayList<>();
        if (words == null || words.length == 0 || s == null || s.isEmpty()) {
            return res;
        }

        int count = words.length, len = words[0].length();
        int border = count * len;
        Map<String, Integer> wordCount = new HashMap<>(), seen = new HashMap<>();

        for (String word : words) {
            wordCount.put(word, wordCount.getOrDefault(word, 0) + 1);
        }
        for (int i = 0; i <= s.length() - border; i++) {
            boolean isValid = true;
            for (int j = 0; j < count; j++) {
                int index = i + j * len;
                String sub = s.substring(index, index + len);
                if (!wordCount.containsKey(sub)) {
                    isValid = false;
                    break;
                }
                seen.put(sub, seen.getOrDefault(sub, 0) + 1);
                if (seen.get(sub) > wordCount.get(sub)) {
                    isValid = false;
                    break;
                }
            }
            if (isValid) {
                res.add(i);
            }
            seen.clear();
        }
        return res;
    }

    /**
     * @desc 最小覆盖子串
     * 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 ""
     */
    public String minWindow(String s, String t) {
        if (s == null || t == null || s.length() < t.length()) return "";
        Map<Character, Integer> tMap = new HashMap<>();
        for (char c : t.toCharArray()) {
            tMap.put(c, tMap.getOrDefault(c, 0) + 1);
        }
        Map<Character, Integer> sMap = new HashMap<>();
        int size = tMap.size();
        int count = 0;
        int left = 0, right = 0;
        int minLeft = 0, minRight = -1;
        int minLength = Integer.MAX_VALUE;

        while (right < s.length()) {
            char c = s.charAt(right);
            sMap.put(c, sMap.getOrDefault(c, 0) + 1);
            if (tMap.containsKey(c) && sMap.get(c).equals(tMap.get(c))) {
                count++;
            }
            // 左指针移动直到不满足条件
            while (left <= right && count == size) {
                c = s.charAt(left);
                if (right - left + 1 < minLength) {
                    minLeft = left;
                    minRight = right;
                    minLength = right - left + 1;
                }
                sMap.put(c, sMap.get(c) - 1);
                if (tMap.containsKey(c) && sMap.get(c) < tMap.get(c)) {
                    count--;
                }
                left++;
            }
            // 右指针移动直到满足条件
            right++;
        }

        return minRight == -1 ? "" : s.substring(minLeft, minRight + 1);
    }


    @Test
    public void test() {
        System.out.println(minWindow("cabwefgewcwaefgcf", "cae"));
    }

    public static void main(String[] args) {
        System.out.println("goooo".substring(0, 1));
    }
}
